package com.huangpeng.algorithm.dataStructure;

/**
 * @Author hp
 * @Title N皇后
 * @Package
 * @Date 2021/8/30 10:14
 * @Description
 * @Version 1.0
 */
public class NQueen {
    private final static int n  = 8;// 皇后数量，可拓展为N皇后
    private static int count = 0;// 总方法数
    private static int limit;

    public static void main(String[] args) {
        limit = (1 << n) - 1;
        backtracking(0,0,0,0);
        System.out.println("总方法数:" + count);
    }

    private static void backtracking(int a, int b, int c, int depth) {
        if(depth == n){
            count ++ ;
            return;
        }
        int d = a | b | c;
        while (d < limit){
            int bit = (d + 1) & ~d;
            backtracking(a | bit,limit & ((b | bit) >> 1),limit & ((c | bit) << 1),depth + 1);
            d |= bit;
        }
    }
}
